This invention concerns the operation of digital computers, and is particularly directed to the processing of branch instructions in a digital computer.
Branch instructions can reduce the speed and efficiency of instruction processing in a computer. This performance penalty is especially severe in computers which perform pipelined instruction processing and is worse still in computers which have multiple pipelined functional units. Branch prediction schemes have been proposed to reduce the performance penalty caused by branch instruction execution. One such scheme involves dynamic prediction of branch outcomes by tagging branch instructions in a cache with predictive information regarding their outcomes. See, for example, the article by J. E. Smith entitled "A Study of Branch Prediction Strategies," in the March 1981 Proceedings of the Eight Annual Symposium on Computer Architecture, and application Ser. No. 07/687,309. Typically, the predictive information is in the form of bits which record the execution history of the associated branch instructions. A single prediction bit is used to record whether the branch was taken or not taken on its most recent execution. When the branch instruction is fetched for execution again, the branch is predicted to take the direction it did last time. If the prediction turns out to be incorrect, the history bit is updated to reflect the actual branch outcome. Multiple prediction bits may be used to facilitate more elaborate prediction schemes. Several multiple bit prediction algorithms are described in the article by J. K. F. Lee and A. J. Smith, entitled "Branch Prediction Strategies in Branch Target Buffer Design," in the January, 1984 issue of IEEE Computer.
Once the history of a branch instruction is established, i.e., after it has been executed at least one time, the outcome of the branch on its next execution can be predicted with a high degree of accuracy. Establishing the initial state of the prediction bits poses a problem, however, since no history information is available when a line is brought into the cache. The simplest solution is to initialize the bits to some arbitrary value, for example, to a value that will cause a "not taken" branch prediction to be made for all branch instructions in the line. Unfortunately, for truly conditional branches, this is seldom more than 50% accurate. Accuracy improves dramatically when actual branch history can be recorded and used for subsequent predictions. It is therefore desirable to retain branch history bits indefinitely, i.e., as long as there is a chance that the associated branch instruction will be executed again. This, however, conflicts with the finite nature of cache storage: a line or block of data, typically data least recently used, may be displaced to make room for a new line of data requested by the processor. For a cache having branch instructions tagged with branch history bits, not only are the cache data discarded but the branch history bits are discarded as well. If the line is ever fetched from memory again and brought back into the cache, the branch history bits must be initialized arbitrarily as described, resulting in decreased instruction processing performance because of decreased branch prediction accuracy.